#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/11 0:38
# @USER    : Shengji He
# @File    : DailyTemperatures.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        """
        Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many
        days you would have to wait until a warmer temperature. If there is no future day for which this is possible,
        put 0 instead.

        For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73],

        your output should be [1, 1, 4, 2, 1, 1, 0, 0].

        Note: The length of temperatures will be in the range [1, 30000].
        Each temperature will be an integer in the range [30, 100].

        :param T: List[int]
        :return: List[int]
        """
        ans = [0] * len(T)
        if len(T) < 2:
            return ans
        for i in range(len(T) - 2, -1, -1):
            next_idx = i + 1
            while True:
                if T[i] < T[next_idx]:
                    ans[i] = next_idx - i
                    break
                elif ans[next_idx] == 0:
                    break
                else:
                    next_idx += ans[next_idx]
        return ans


if __name__ == '__main__':
    S = Solution()
    T = [73, 74, 75, 71, 69, 72, 76, 73]
    print(S.dailyTemperatures(T))
    print('done')
